SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Recurrence relation</title>

</head>

Recurrence relation

</h1>

</header>

In <a href="Mathematics" title="Mathematics">mathematics</a>, a recurrence relation is an <a href="Equation" title="Equation">equation</a> according to which the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">th term of a <a href="Sequence" title="Sequence">sequence</a> of numbers is equal to some combination of the previous terms. Often, only <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> previous terms of the sequence appear in the equation, for a parameter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> that is independent of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">; this number <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> is called the order of the relation. If the values of the first <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> numbers in the sequence have been given, the rest of the sequence can be calculated by repeatedly applying the equation.

In linear recurrences, the nth term is equated to a <a href="Linear_function" title="Linear function">linear function</a> of the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> previous terms. A famous example is the recurrence for the <a href="Fibonacci_number" class="mw-redirect" title="Fibonacci number">Fibonacci numbers</a>,

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{n}=F_{n-1}+F_{n-2}}</annotation>

</semantics>

</math>

where the order <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> is two and the linear function merely adds the two previous terms. This example is a <a href="Linear_recurrence_with_constant_coefficients" title="Linear recurrence with constant coefficients">linear recurrence with constant coefficients</a>, because the coefficients of the linear function (1 and 1) are constants that do not depend on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n.}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n.}</annotation>

</semantics>

</math><img src="./e59df02a9f67a5da3c220f1244c99a46cc4eb1c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.042ex; height:1.676ex;" alt="{\displaystyle n.}" loading="lazy"> For these recurrences, one can express the general term of the sequence as a <a href="Closed-form_expression" title="Closed-form expression">closed-form expression</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">. As well, <a href="P-recursive_equation" title="P-recursive equation">linear recurrences with polynomial coefficients</a> depending on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> are also important, because many common <a href="Elementary_functions" class="mw-redirect" title="Elementary functions">elementary functions</a> and <a href="Special_functions" title="Special functions">special functions</a> have a <a href="Taylor_series" title="Taylor series">Taylor series</a> whose coefficients satisfy such a recurrence relation (see <a href="Holonomic_function" title="Holonomic function">holonomic function</a>).

Solving a recurrence relation means obtaining a <a href="Closed-form_solution" class="mw-redirect" title="Closed-form solution">closed-form solution</a>: a non-recursive function of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">.

The concept of a recurrence relation can be extended to <a href="Multidimensional_array" class="mw-redirect" title="Multidimensional array">multidimensional arrays</a>, that is, <a href="Indexed_families" class="mw-redirect" title="Indexed families">indexed families</a> that are indexed by <a href="Tuple" title="Tuple">tuples</a> of <a href="Natural_number" title="Natural number">natural numbers</a>.

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

A recurrence relation is an equation that expresses each element of a <a href="Sequence" title="Sequence">sequence</a> as a function of the preceding ones. More precisely, in the case where only the immediately preceding element is involved, a recurrence relation has the form

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u_{n}=\varphi (n,u_{n-1})\quad {\text{for}}\quad n>0,}</annotation>

</semantics>

</math><img src="./b39e6366097c9c3c9fb8f9f1c4baaa3b927193b5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.787ex; height:2.843ex;" alt="{\displaystyle u_{n}=\varphi (n,u_{n-1})\quad {\text{for}}\quad n>0,}" loading="lazy"></dd></dl>

where

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi :\mathbb {N} \times X\to X}</annotation>

</semantics>

</math><img src="./c3052fefd057a5bb64708000b6fee73a4896e8d8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.55ex; height:2.676ex;" alt="{\displaystyle \varphi :\mathbb {N} \times X\to X}" loading="lazy"></dd></dl>

is a function, where X is a set to which the elements of a sequence must belong. For any <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u_{0}\in X}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u_{0}\in X}</annotation>

</semantics>

</math><img src="./8fa036cfc6caa529e76fa776fb44cd2a131055f0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.205ex; height:2.509ex;" alt="{\displaystyle u_{0}\in X}" loading="lazy">, this defines a unique sequence with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u_{0}}</annotation>

</semantics>

</math><img src="./9c7425f9c7ab645587060423c0af62f8a61fbc65.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle u_{0}}" loading="lazy"> as its first element, called the initial value.<a href="#cite_note-1">[1]</a>

It is easy to modify the definition for getting sequences starting from the term of index 1 or higher.

This defines recurrence relation of first order. A recurrence relation of order k has the form

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u_{n}=\varphi (n,u_{n-1},u_{n-2},\ldots ,u_{n-k})\quad {\text{for}}\quad n\geq k,}</annotation>

</semantics>

</math><img src="./dc64191a5d3a0de09e832edbfddbe8d1ff2e3b63.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:45.38ex; height:2.843ex;" alt="{\displaystyle u_{n}=\varphi (n,u_{n-1},u_{n-2},\ldots ,u_{n-k})\quad {\text{for}}\quad n\geq k,}" loading="lazy"></dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi :\mathbb {N} \times X^{k}\to X}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi :\mathbb {N} \times X^{k}\to X}</annotation>

</semantics>

</math><img src="./636bd3ed7c1d6eccf3d5dcf4fea980cd20cd98f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.655ex; height:3.176ex;" alt="{\displaystyle \varphi :\mathbb {N} \times X^{k}\to X}" loading="lazy"> is a function that involves k consecutive elements of the sequence.

In this case, k initial values are needed for defining a sequence.

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Factorial">Factorial</h3></div>

The <a href="Factorial" title="Factorial">factorial</a> is defined by the recurrence relation

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n!=n\cdot (n-1)!\quad {\text{for}}\quad n>0,}</annotation>

</semantics>

</math><img src="./bf40ba566fa3597f946022d9d63847e21bffacc7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.801ex; height:2.843ex;" alt="{\displaystyle n!=n\cdot (n-1)!\quad {\text{for}}\quad n>0,}" loading="lazy"></dd></dl>

and the initial condition

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0!=1.}</annotation>

</semantics>

</math><img src="./73b6aeeba784d2992f64addf82d9cbbf7962a722.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.717ex; height:2.176ex;" alt="{\displaystyle 0!=1.}" loading="lazy"></dd></dl>

This is an example of a linear recurrence with polynomial coefficients of order 1, with the simple polynomial (in n)

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></dd></dl>

as its only coefficient.

<div class="mw-heading mw-heading3"><h3 id="Logistic_map">Logistic map</h3></div>

An example of a recurrence relation is the <a href="Logistic_map" title="Logistic map">logistic map</a> defined by

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{n+1}=rx_{n}(1-x_{n}),}</annotation>

</semantics>

</math><img src="./226aeceae0973efe53ac663deee45e7558641ef7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.351ex; height:2.843ex;" alt="{\displaystyle x_{n+1}=rx_{n}(1-x_{n}),}" loading="lazy"></dd></dl>

for a given constant <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r.}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r.}</annotation>

</semantics>

</math><img src="./10110093812676dd04a92ce4c8b75940c366330a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.695ex; height:1.676ex;" alt="{\displaystyle r.}" loading="lazy"> The behavior of the sequence depends dramatically on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r,}</annotation>

</semantics>

</math><img src="./250644a0f511e9078be6f89ba78a606a0e08c0a0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.695ex; height:2.009ex;" alt="{\displaystyle r,}" loading="lazy"> but is stable when the initial condition <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{0}}</annotation>

</semantics>

</math><img src="./86f21d0e31751534cd6584264ecf864a6aa792cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{0}}" loading="lazy"> varies.

<div class="mw-heading mw-heading3"><h3 id="Fibonacci_numbers">Fibonacci numbers</h3></div>

The recurrence of order two satisfied by the <a href="Fibonacci_number" class="mw-redirect" title="Fibonacci number">Fibonacci numbers</a> is the canonical example of a homogeneous <a href="Linear_recurrence" class="mw-redirect" title="Linear recurrence">linear recurrence</a> relation with constant coefficients (see below). The Fibonacci sequence is defined using the recurrence

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{n}=F_{n-1}+F_{n-2}}</annotation>

</semantics>

</math><img src="./4fa6d281e7a54e08aeffeef7458ddc0884333686.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.279ex; height:2.509ex;" alt="{\displaystyle F_{n}=F_{n-1}+F_{n-2}}" loading="lazy"></dd></dl>

with <a href="Initial_condition" title="Initial condition">initial conditions</a>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{0}=0}</annotation>

</semantics>

</math><img src="./58ebe8b2d5551fb272cd4258940fe1e492592d02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.81ex; height:2.509ex;" alt="{\displaystyle F_{0}=0}" loading="lazy"></dd>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{1}=1.}</annotation>

</semantics>

</math><img src="./d82a44cb65b9767e423f88c055237e1504e4bcb6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.457ex; height:2.509ex;" alt="{\displaystyle F_{1}=1.}" loading="lazy"></dd></dl>

Explicitly, the recurrence yields the equations

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{2}=F_{1}+F_{0}}</annotation>

</semantics>

</math><img src="./895ca91b2446c20aba1d650fa20437fa064bfcf5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.585ex; height:2.509ex;" alt="{\displaystyle F_{2}=F_{1}+F_{0}}" loading="lazy"></dd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{3}=F_{2}+F_{1}}</annotation>

</semantics>

</math><img src="./d9c90153e3bd38ce7f3375e5c4ab4f6b8106dea4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.585ex; height:2.509ex;" alt="{\displaystyle F_{3}=F_{2}+F_{1}}" loading="lazy"></dd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{4}=F_{3}+F_{2}}</annotation>

</semantics>

</math><img src="./9bad5948bccb2781a37e369dc1b97fba9b38d258.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.585ex; height:2.509ex;" alt="{\displaystyle F_{4}=F_{3}+F_{2}}" loading="lazy"></dd></dl>

etc.

We obtain the sequence of Fibonacci numbers, which begins

The recurrence can be solved by methods described below yielding <a href="Binet's_formula" class="mw-redirect" title="Binet's formula">Binet's formula</a>, which involves powers of the two roots of the characteristic polynomial <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t^{2}=t+1}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t^{2}=t+1}</annotation>

</semantics>

</math><img src="./ee084dc168cdb757b23a5ed32585e0f0ed62d07a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.835ex; height:2.843ex;" alt="{\displaystyle t^{2}=t+1}" loading="lazy">; the <a href="Generating_function" title="Generating function">generating function</a> of the sequence is the <a href="Rational_function" title="Rational function">rational function</a>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {t}{1-t-t^{2}}}.}</annotation>

</semantics>

</math><img src="./42aff93fdb2df6bc6a094938742ec016b61c9e8d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:11.06ex; height:5.676ex;" alt="{\displaystyle {\frac {t}{1-t-t^{2}}}.}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Binomial_coefficients">Binomial coefficients</h3></div>

A simple example of a multidimensional recurrence relation is given by the <a href="Binomial_coefficient" title="Binomial coefficient">binomial coefficients</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tbinom {n}{k}}}">

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tbinom {n}{k}}}</annotation>

</semantics>

</math><img src="./206415d3742167e319b2e52c2ca7563b799abad7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.116ex; height:3.176ex;" alt="{\displaystyle {\tbinom {n}{k}}}" loading="lazy">, which count the ways of selecting <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> elements out of a set of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> elements.

They can be computed by the recurrence relation

<mrow>

</mrow>

</mfrac>

</mrow>

<mrow>

</mrow>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},}</annotation>

</semantics>

</math><img src="./0ad549fc68ce9889ccb2b4cd29f105c9436926f7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:29.039ex; height:6.176ex;" alt="{\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},}" loading="lazy"></dd></dl>

with the base cases <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tbinom {n}{0}}={\tbinom {n}{n}}=1}">

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tbinom {n}{0}}={\tbinom {n}{n}}=1}</annotation>

</semantics>

</math><img src="./ee3b9f0db57e10bee739c775d1f9c4a70b51fa7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:13.591ex; height:3.343ex;" alt="{\displaystyle {\tbinom {n}{0}}={\tbinom {n}{n}}=1}" loading="lazy">. Using this formula to compute the values of all binomial coefficients generates an infinite array called <a href="Pascal's_triangle" title="Pascal's triangle">Pascal's triangle</a>. The same values can also be computed directly by a different formula that is not a recurrence, but uses <a href="Factorial" title="Factorial">factorials</a>, multiplication and division, not just additions:

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.}</annotation>

</semantics>

</math><img src="./a2457a7ef3c77831e34e06a1fe17a80b84a03181.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:19.158ex; height:6.343ex;" alt="{\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.}" loading="lazy"></dd></dl>

The binomial coefficients can also be computed with a uni-dimensional recurrence:

<mrow>

</mrow>

</mfrac>

</mrow>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\binom {n}{k}}={\binom {n}{k-1}}(n-k+1)/k,}</annotation>

</semantics>

</math><img src="./4e08292b308bd9d0bfbecb4910f4dd9af2cb6b0b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:30.829ex; height:6.176ex;" alt="{\displaystyle {\binom {n}{k}}={\binom {n}{k-1}}(n-k+1)/k,}" loading="lazy"></dd></dl>

with the initial value <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle {\binom {n}{0}}=1}">

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle {\binom {n}{0}}=1}</annotation>

</semantics>

</math><img src="./73446ccea3a40be047822b65fa45d8619b7a16f3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:7.377ex; height:3.343ex;" alt="{\textstyle {\binom {n}{0}}=1}" loading="lazy"> (The division is not displayed as a fraction for emphasizing that it must be computed after the multiplication, for not introducing fractional numbers).

This recurrence is widely used in computers because it does not require to build a table as does the bi-dimensional recurrence, and does not involve very large integers as does the formula with factorials (if one uses <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle {\binom {n}{k}}={\binom {n}{n-k}},}">

<mrow>

</mrow>

</mfrac>

</mrow>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle {\binom {n}{k}}={\binom {n}{n-k}},}</annotation>

</semantics>

</math><img src="./a5996de36d28a2805a72610575a48bb84fa3ca96.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:12.112ex; height:3.343ex;" alt="{\textstyle {\binom {n}{k}}={\binom {n}{n-k}},}" loading="lazy"> all involved integers are smaller than the final result).

<div class="mw-heading mw-heading2"><h2 id="Difference_operator_and_difference_equations">Difference operator and difference equations </h2></div>

The <style data-mw-deduplicate="TemplateStyles:r1238216509">

/* start https://en.wikipedia.org/ */

.mw-parser-output .vanchor>:target~.vanchor-text{background-color:#b1d2ff}@media screen{html.skin-theme-clientpref-night .mw-parser-output .vanchor>:target~.vanchor-text{background-color:#0f4dc9}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .vanchor>:target~.vanchor-text{background-color:#0f4dc9}}

/* end https://en.wikipedia.org/ */

</style>difference operator is an <a href="Operator_(mathematics)" title="Operator (mathematics)">operator</a> that maps <a href="Sequence" title="Sequence">sequences</a> to sequences, and, more generally, <a href="Function_(mathematics)" title="Function (mathematics)">functions</a> to functions. It is commonly denoted <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta ,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta ,}</annotation>

</semantics>

</math><img src="./54793fbbac10eddbdedded44e39ff274fffa8466.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.583ex; height:2.509ex;" alt="{\displaystyle \Delta ,}" loading="lazy"> and is defined, in <a href="Functional_notation" class="mw-redirect" title="Functional notation">functional notation</a>, as

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\Delta f)(x)=f(x+1)-f(x).}</annotation>

</semantics>

</math><img src="./45a83177c48fa871f2fa957af6a65f4e642b980b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.586ex; height:2.843ex;" alt="{\displaystyle (\Delta f)(x)=f(x+1)-f(x).}" loading="lazy"></dd></dl>

It is thus a special case of <a href="Finite_difference" title="Finite difference">finite difference</a>.

When using the index notation for sequences, the definition becomes

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\Delta a)_{n}=a_{n+1}-a_{n}.}</annotation>

</semantics>

</math><img src="./869ed8884c385b4fb67194d49223b64786fd167b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.776ex; height:2.843ex;" alt="{\displaystyle (\Delta a)_{n}=a_{n+1}-a_{n}.}" loading="lazy"></dd></dl>

The parentheses around <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta f}</annotation>

</semantics>

</math><img src="./ff38db24bc80b80a0a1ecfce75f3dca3fc79d54e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.214ex; height:2.509ex;" alt="{\displaystyle \Delta f}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta a}</annotation>

</semantics>

</math><img src="./e7b918c3be22dcf988d83e39f3e10ed95961d7cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.166ex; height:2.176ex;" alt="{\displaystyle \Delta a}" loading="lazy"> are generally omitted, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta a_{n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta a_{n}}</annotation>

</semantics>

</math><img src="./06e7ffdcaa7ef6d3f0c4b01a4b3a5eb05d80ed50.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.384ex; height:2.509ex;" alt="{\displaystyle \Delta a_{n}}" loading="lazy"> must be understood as the term of index n in the sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta a,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta a,}</annotation>

</semantics>

</math><img src="./e7a0aa80acae2fb11353227a1a5973c026cefbc5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.813ex; height:2.509ex;" alt="{\displaystyle \Delta a,}" loading="lazy"> and not <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta }</annotation>

</semantics>

</math><img src="./32769037c408874e1890f77554c65f39c523ebe2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.936ex; height:2.176ex;" alt="{\displaystyle \Delta }" loading="lazy"> applied to the element <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{n}.}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{n}.}</annotation>

</semantics>

</math><img src="./cb4733ab60320bf912d93dce5a27ccd1dca7e905.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.095ex; height:2.009ex;" alt="{\displaystyle a_{n}.}" loading="lazy">

Given <a href="Sequence" title="Sequence">sequence</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a=(a_{n})_{n\in \mathbb {N} },}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a=(a_{n})_{n\in \mathbb {N} },}</annotation>

</semantics>

</math><img src="./f2487fd91d1b920989c4a31a7020a087e75cd695.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.734ex; height:2.843ex;" alt="{\displaystyle a=(a_{n})_{n\in \mathbb {N} },}" loading="lazy"> the first difference of a is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta a.}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta a.}</annotation>

</semantics>

</math><img src="./dba6ed7246c97cacee7400369b3703cc55e017bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.813ex; height:2.176ex;" alt="{\displaystyle \Delta a.}" loading="lazy">

The second difference is

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta ^{2}a=(\Delta \circ \Delta )a=\Delta (\Delta a).}</annotation>

</semantics>

</math><img src="./dd9c089c0041d9ee2cc7a8712868530c777194c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.08ex; height:3.176ex;" alt="{\displaystyle \Delta ^{2}a=(\Delta \circ \Delta )a=\Delta (\Delta a).}" loading="lazy"> A simple computation shows that

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta ^{2}a_{n}=a_{n+2}-2a_{n+1}+a_{n}.}</annotation>

</semantics>

</math><img src="./1323979dd8e68afc837f26475ae81cbfdc580a0c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:27.573ex; height:3.009ex;" alt="{\displaystyle \Delta ^{2}a_{n}=a_{n+2}-2a_{n+1}+a_{n}.}" loading="lazy"></dd></dl>

More generally: the kth difference is defined recursively as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta ^{k}=\Delta \circ \Delta ^{k-1},}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta ^{k}=\Delta \circ \Delta ^{k-1},}</annotation>

</semantics>

</math><img src="./951627dd1ea774191182e78953b6be644660a74a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.026ex; height:3.009ex;" alt="{\displaystyle \Delta ^{k}=\Delta \circ \Delta ^{k-1},}" loading="lazy"> and one has

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

<mrow>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta ^{k}a_{n}=\sum _{t=0}^{k}(-1)^{t}{\binom {k}{t}}a_{n+k-t}.}</annotation>

</semantics>

</math><img src="./9ebbb3309411cff5f500965b15457104897040ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:29.267ex; height:7.343ex;" alt="{\displaystyle \Delta ^{k}a_{n}=\sum _{t=0}^{k}(-1)^{t}{\binom {k}{t}}a_{n+k-t}.}" loading="lazy"></dd></dl>

This relation can be inverted, giving

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{n+k}=a_{n}+{k \choose 1}\Delta a_{n}+\cdots +{k \choose k}\Delta ^{k}(a_{n}).}</annotation>

</semantics>

</math><img src="./002031d3418daf77ada3c0aebb352e4b33ccca41.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:42.952ex; height:6.176ex;" alt="{\displaystyle a_{n+k}=a_{n}+{k \choose 1}\Delta a_{n}+\cdots +{k \choose k}\Delta ^{k}(a_{n}).}" loading="lazy"></dd></dl>

A difference equation of order k is an equation that involves the k first differences of a sequence or a function, in the same way as a <a href="Ordinary_differential_equation" title="Ordinary differential equation">differential equation</a> of order k relates the k first <a href="Derivative" title="Derivative">derivatives</a> of a function.

The two above relations allow transforming a recurrence relation of order k into a difference equation of order k, and, conversely, a difference equation of order k into recurrence relation of order k. Each transformation is the <a href="Inverse_function" title="Inverse function">inverse</a> of the other, and the sequences that are solution of the difference equation are exactly those that satisfies the recurrence relation.

For example, the difference equation

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 3\Delta ^{2}a_{n}+2\Delta a_{n}+7a_{n}=0}</annotation>

</semantics>

</math><img src="./fa076588fb37d8f64245e804d28ce01527094635.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:25.7ex; height:3.009ex;" alt="{\displaystyle 3\Delta ^{2}a_{n}+2\Delta a_{n}+7a_{n}=0}" loading="lazy"></dd></dl>

is equivalent to the recurrence relation

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 3a_{n+2}=4a_{n+1}-8a_{n},}</annotation>

</semantics>

</math><img src="./7b09b5f32e60bb203d991238aa3fa906701e4d99.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:21.619ex; height:2.509ex;" alt="{\displaystyle 3a_{n+2}=4a_{n+1}-8a_{n},}" loading="lazy"></dd></dl>

in the sense that the two equations are satisfied by the same sequences.

As it is equivalent for a sequence to satisfy a recurrence relation or to be the solution of a difference equation, the two terms "recurrence relation" and "difference equation" are sometimes used interchangeably. See <a href="Rational_difference_equation" title="Rational difference equation">Rational difference equation</a> and <a href="Matrix_difference_equation" title="Matrix difference equation">Matrix difference equation</a> for example of uses of "difference equation" instead of "recurrence relation"

Difference equations resemble differential equations, and this resemblance is often used to mimic methods for solving differentiable equations to apply to solving difference equations, and therefore recurrence relations.

<a href="Summation_equation" title="Summation equation">Summation equations</a> relate to difference equations as <a href="Integral_equation" title="Integral equation">integral equations</a> relate to differential equations. See <a href="Time_scale_calculus" class="mw-redirect" title="Time scale calculus">time scale calculus</a> for a unification of the theory of difference equations with that of differential equations.

<div class="mw-heading mw-heading3"><h3 id="From_sequences_to_grids">From sequences to grids</h3></div>

Single-variable or one-dimensional recurrence relations are about sequences (i.e. functions defined on one-dimensional grids). Multi-variable or n-dimensional recurrence relations are about <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">-dimensional grids. Functions defined on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">-grids can also be studied with partial difference equations.<a href="#cite_note-2">[2]</a>

<div class="mw-heading mw-heading2"><h2 id="Solving">Solving</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Solving_linear_recurrence_relations_with_constant_coefficients">Solving linear recurrence relations with constant coefficients</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Linear_recurrence_with_constant_coefficients" title="Linear recurrence with constant coefficients">Linear recurrence with constant coefficients</a></div>

<div class="mw-heading mw-heading3"><h3 id="Solving_first-order_non-homogeneous_recurrence_relations_with_variable_coefficients">Solving first-order non-homogeneous recurrence relations with variable coefficients</h3></div>

Moreover, for the general first-order non-homogeneous linear recurrence relation with variable coefficients:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{n+1}=f_{n}a_{n}+g_{n},\qquad f_{n}\neq 0,}</annotation>

</semantics>

</math><img src="./8c6f3cb8cc40110dc2469832ef2610375a2f20c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:30.566ex; height:2.676ex;" alt="{\displaystyle a_{n+1}=f_{n}a_{n}+g_{n},\qquad f_{n}\neq 0,}" loading="lazy"></dd></dl>

there is also a nice method to solve it:<a href="#cite_note-3">[3]</a>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{n+1}-f_{n}a_{n}=g_{n}}</annotation>

</semantics>

</math><img src="./2eb6faebeeca42ce59b1cb98b3026f910a28d0ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.621ex; height:2.509ex;" alt="{\displaystyle a_{n+1}-f_{n}a_{n}=g_{n}}" loading="lazy"></dd>

<mfrac>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mfrac>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {a_{n+1}}{\prod _{k=0}^{n}f_{k}}}-{\frac {f_{n}a_{n}}{\prod _{k=0}^{n}f_{k}}}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}}</annotation>

</semantics>

</math><img src="./493c9e0bb1f95e3bb7a4bc9c036b6f641695000f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:32.441ex; height:6.343ex;" alt="{\displaystyle {\frac {a_{n+1}}{\prod _{k=0}^{n}f_{k}}}-{\frac {f_{n}a_{n}}{\prod _{k=0}^{n}f_{k}}}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}}" loading="lazy"></dd></dl>

<mfrac>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mfrac>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mfrac>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {a_{n+1}}{\prod _{k=0}^{n}f_{k}}}-{\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}}</annotation>

</semantics>

</math><img src="./6a9f5ef658eed08148a305dcb01e46788dedcabe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:32.571ex; height:6.176ex;" alt="{\displaystyle {\frac {a_{n+1}}{\prod _{k=0}^{n}f_{k}}}-{\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}}" loading="lazy"></dd></dl>

Let

<msub>

</mrow>

</msub>

<mfrac>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{n}={\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}},}</annotation>

</semantics>

</math><img src="./17c893a3d10387a0e30d23ec17df41bed06f1e09.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:15.671ex; height:6.009ex;" alt="{\displaystyle A_{n}={\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}},}" loading="lazy"></dd></dl>

Then

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mfrac>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{n+1}-A_{n}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}}</annotation>

</semantics>

</math><img src="./1767d27449fcc02d3d9093fa6cf221d342184c5e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:22.797ex; height:5.843ex;" alt="{\displaystyle A_{n+1}-A_{n}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}}" loading="lazy"></dd>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<mfrac>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{m=0}^{n-1}(A_{m+1}-A_{m})=A_{n}-A_{0}=\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}}</annotation>

</semantics>

</math><img src="./1302032ef27d12d183c8cb69c0c2a300ae57bbb1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:44.691ex; height:7.343ex;" alt="{\displaystyle \sum _{m=0}^{n-1}(A_{m+1}-A_{m})=A_{n}-A_{0}=\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}}" loading="lazy"></dd>

<mfrac>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<mfrac>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}}=A_{0}+\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}}</annotation>

</semantics>

</math><img src="./d359db8ee1a7855aafd586032d6435762dc363fe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:30.465ex; height:7.509ex;" alt="{\displaystyle {\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}}=A_{0}+\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}}" loading="lazy"></dd>

<msub>

</mrow>

</msub>

<mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<mfrac>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{n}=\left(\prod _{k=0}^{n-1}f_{k}\right)\left(A_{0}+\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}\right)}</annotation>

</semantics>

</math><img src="./f6fb1b764320c643c0a73ee67b534fb9d8aaadb3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:37.401ex; height:7.509ex;" alt="{\displaystyle a_{n}=\left(\prod _{k=0}^{n-1}f_{k}\right)\left(A_{0}+\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}\right)}" loading="lazy"></dd></dl>

If we apply the formula to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{n+1}=(1+hf_{nh})a_{n}+hg_{nh}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{n+1}=(1+hf_{nh})a_{n}+hg_{nh}}</annotation>

</semantics>

</math><img src="./48ab092a882a521a08e538e363de50b3d598ade3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.005ex; height:2.843ex;" alt="{\displaystyle a_{n+1}=(1+hf_{nh})a_{n}+hg_{nh}}" loading="lazy"> and take the limit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h\to 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h\to 0}</annotation>

</semantics>

</math><img src="./3f15c1e6800f6e3fca9fec99720fc67a13780215.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.116ex; height:2.176ex;" alt="{\displaystyle h\to 0}" loading="lazy">, we get the formula for first order <a href="Linear_differential_equation" title="Linear differential equation">linear differential equations</a> with variable coefficients; the sum becomes an integral, and the product becomes the exponential function of an integral.

<div class="mw-heading mw-heading3"><h3 id="Solving_general_homogeneous_linear_recurrence_relations">Solving general homogeneous linear recurrence relations</h3></div>

Many homogeneous linear recurrence relations may be solved by means of the <a href="Generalized_hypergeometric_series" class="mw-redirect" title="Generalized hypergeometric series">generalized hypergeometric series</a>. Special cases of these lead to recurrence relations for the <a href="Orthogonal_polynomials" title="Orthogonal polynomials">orthogonal polynomials</a>, and many <a href="Special_function" class="mw-redirect" title="Special function">special functions</a>. For example, the solution to

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle J_{n+1}={\frac {2n}{z}}J_{n}-J_{n-1}}</annotation>

</semantics>

</math><img src="./2533ad51ccedceef2132a0238a07696abc7c9e20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:21.059ex; height:5.176ex;" alt="{\displaystyle J_{n+1}={\frac {2n}{z}}J_{n}-J_{n-1}}" loading="lazy"></dd></dl>

is given by

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle J_{n}=J_{n}(z),}</annotation>

</semantics>

</math><img src="./a264849a28815e59613d08e70ab4c0f5200883fd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.66ex; height:2.843ex;" alt="{\displaystyle J_{n}=J_{n}(z),}" loading="lazy"></dd></dl>

the <a href="Bessel_function" title="Bessel function">Bessel function</a>, while

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (b-n)M_{n-1}+(2n-b+z)M_{n}-nM_{n+1}=0}</annotation>

</semantics>

</math><img src="./3b4edbf5b7dce895d3a0fbf1411fed6e1e21d42f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:45.13ex; height:2.843ex;" alt="{\displaystyle (b-n)M_{n-1}+(2n-b+z)M_{n}-nM_{n+1}=0}" loading="lazy"></dd></dl>

is solved by

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{n}=M(n,b;z)}</annotation>

</semantics>

</math><img src="./254aa40519bb2f8811b933b8cdfa5df9f80bc2b3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.371ex; height:2.843ex;" alt="{\displaystyle M_{n}=M(n,b;z)}" loading="lazy"></dd></dl>

the <a href="Confluent_hypergeometric_series" class="mw-redirect" title="Confluent hypergeometric series">confluent hypergeometric series</a>. Sequences which are the solutions of <a href="P-recursive_equation" title="P-recursive equation">linear difference equations with polynomial coefficients</a> are called <a href="Holonomic_function" title="Holonomic function">P-recursive</a>. For these specific recurrence equations algorithms are known which find <a href="Polynomial_solutions_of_P-recursive_equations" title="Polynomial solutions of P-recursive equations">polynomial</a>, <a href="Abramov's_algorithm" title="Abramov's algorithm">rational</a> or <a href="Petkov%C5%A1ek's_algorithm" title="Petkovšek's algorithm">hypergeometric</a> solutions.

<div class="mw-heading mw-heading3"><h3 id="Solving_general_non-homogeneous_linear_recurrence_relations_with_constant_coefficients">Solving general non-homogeneous linear recurrence relations with constant coefficients</h3></div>

Furthermore, for the general non-homogeneous linear recurrence relation with constant coefficients, one can solve it based on variation of parameter.<a href="#cite_note-4">[4]</a>

<div class="mw-heading mw-heading3"><h3 id="Solving_first-order_rational_difference_equations">Solving first-order rational difference equations</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Rational_difference_equation" title="Rational difference equation">Rational difference equation</a></div>

A first order rational difference equation has the form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{t+1}={\tfrac {aw_{t}+b}{cw_{t}+d}}}">

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{t+1}={\tfrac {aw_{t}+b}{cw_{t}+d}}}</annotation>

</semantics>

</math><img src="./0df7317788065d7f493313f16b85fc7ae5b925e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.505ex; width:13.202ex; height:4.176ex;" alt="{\displaystyle w_{t+1}={\tfrac {aw_{t}+b}{cw_{t}+d}}}" loading="lazy">. Such an equation can be solved by writing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{t}}</annotation>

</semantics>

</math><img src="./6cc7b029066adbf68868f39f3dceb58eab2d1a12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.49ex; height:2.009ex;" alt="{\displaystyle w_{t}}" loading="lazy"> as a nonlinear transformation of another variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{t}}</annotation>

</semantics>

</math><img src="./f279a30bc8eabc788f3fe81c9cfb674e72e858db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.156ex; height:2.009ex;" alt="{\displaystyle x_{t}}" loading="lazy"> which itself evolves linearly. Then standard methods can be used to solve the linear difference equation in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{t}}</annotation>

</semantics>

</math><img src="./f279a30bc8eabc788f3fe81c9cfb674e72e858db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.156ex; height:2.009ex;" alt="{\displaystyle x_{t}}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Stability">Stability</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Stability_of_linear_higher-order_recurrences">Stability of linear higher-order recurrences</h3></div>

The linear recurrence of order <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy">,

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d},}</annotation>

</semantics>

</math><img src="./685b8c6fbeefa248e236c9028ef26bcd91d03b60.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:37.343ex; height:2.343ex;" alt="{\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d},}" loading="lazy"></dd></dl>

has the <a href="Characteristic_polynomial" title="Characteristic polynomial">characteristic equation</a>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda ^{d}-c_{1}\lambda ^{d-1}-c_{2}\lambda ^{d-2}-\cdots -c_{d}\lambda ^{0}=0.}</annotation>

</semantics>

</math><img src="./60d69b455bfd51004f3dd90a2a4b3eb82e4e51ac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:39.166ex; height:3.009ex;" alt="{\displaystyle \lambda ^{d}-c_{1}\lambda ^{d-1}-c_{2}\lambda ^{d-2}-\cdots -c_{d}\lambda ^{0}=0.}" loading="lazy"></dd></dl>

The recurrence is <a href="Stability_theory" title="Stability theory">stable</a>, meaning that the iterates converge asymptotically to a fixed value, if and only if the <a href="Eigenvalues" class="mw-redirect" title="Eigenvalues">eigenvalues</a> (i.e., the roots of the characteristic equation), whether real or complex, are all less than <a href="Unity_(mathematics)" class="mw-redirect" title="Unity (mathematics)">unity</a> in absolute value.

<div class="mw-heading mw-heading3"><h3 id="Stability_of_linear_first-order_matrix_recurrences">Stability of linear first-order matrix recurrences</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Matrix_difference_equation" title="Matrix difference equation">Matrix difference equation</a></div>

In the first-order matrix difference equation

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [x_{t}-x^{*}]=A[x_{t-1}-x^{*}]}</annotation>

</semantics>

</math><img src="./d44efeb30b7983e82f620c399f4e7c04483de5c8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.289ex; height:2.843ex;" alt="{\displaystyle [x_{t}-x^{*}]=A[x_{t-1}-x^{*}]}" loading="lazy"></dd></dl>

with state vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> and transition matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> converges asymptotically to the steady state vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*}}</annotation>

</semantics>

</math><img src="./e5be23ee5d433f8b576e63bcb47518128ee0b6bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.343ex;" alt="{\displaystyle x^{*}}" loading="lazy"> if and only if all eigenvalues of the transition matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> (whether real or complex) have an <a href="Absolute_value" title="Absolute value">absolute value</a> which is less than 1.

<div class="mw-heading mw-heading3"><h3 id="Stability_of_nonlinear_first-order_recurrences">Stability of nonlinear first-order recurrences</h3></div>

Consider the nonlinear first-order recurrence

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{n}=f(x_{n-1}).}</annotation>

</semantics>

</math><img src="./91f76b42f234f94f0fc24136a163086d503bfc78.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.03ex; height:2.843ex;" alt="{\displaystyle x_{n}=f(x_{n-1}).}" loading="lazy"></dd></dl>

This recurrence is <a href="Stability_theory" title="Stability theory">locally stable</a>, meaning that it <a href="Limit_of_a_sequence" title="Limit of a sequence">converges</a> to a fixed point <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*}}</annotation>

</semantics>

</math><img src="./e5be23ee5d433f8b576e63bcb47518128ee0b6bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.343ex;" alt="{\displaystyle x^{*}}" loading="lazy"> from points sufficiently close to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*}}</annotation>

</semantics>

</math><img src="./e5be23ee5d433f8b576e63bcb47518128ee0b6bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.343ex;" alt="{\displaystyle x^{*}}" loading="lazy">, if the slope of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> in the neighborhood of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*}}</annotation>

</semantics>

</math><img src="./e5be23ee5d433f8b576e63bcb47518128ee0b6bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.343ex;" alt="{\displaystyle x^{*}}" loading="lazy"> is smaller than <a href="Unity_(mathematics)" class="mw-redirect" title="Unity (mathematics)">unity</a> in absolute value: that is,

</mrow>

<msup>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |f'(x^{*})|<1.}</annotation>

</semantics>

</math><img src="./e795ea0f80d3fbd2139844b80d807ac71da87c8f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.4ex; height:3.009ex;" alt="{\displaystyle |f'(x^{*})|<1.}" loading="lazy"></dd></dl>

A nonlinear recurrence could have multiple fixed points, in which case some fixed points may be locally stable and others locally unstable; for continuous f two adjacent fixed points cannot both be locally stable.

A nonlinear recurrence relation could also have a cycle of period <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k>1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k>1}</annotation>

</semantics>

</math><img src="./5cda43bd4034dc2d04cd562005d0af81d3d2dbc6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.472ex; height:2.176ex;" alt="{\displaystyle k>1}" loading="lazy">. Such a cycle is stable, meaning that it attracts a set of initial conditions of positive measure, if the composite function

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x):=f\circ f\circ \cdots \circ f(x)}</annotation>

</semantics>

</math><img src="./cb4b004d2740de93a11057409443fc768fbd4b5b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.282ex; height:2.843ex;" alt="{\displaystyle g(x):=f\circ f\circ \cdots \circ f(x)}" loading="lazy"></dd></dl>

with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> appearing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> times is locally stable according to the same criterion:

</mrow>

<msup>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |g'(x^{*})|<1,}</annotation>

</semantics>

</math><img src="./f3db7609bf813bcd6093e6284b867f5a720d714f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.198ex; height:3.009ex;" alt="{\displaystyle |g'(x^{*})|<1,}" loading="lazy"></dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*}}</annotation>

</semantics>

</math><img src="./e5be23ee5d433f8b576e63bcb47518128ee0b6bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.343ex;" alt="{\displaystyle x^{*}}" loading="lazy"> is any point on the cycle.

In a <a href="Chaos_theory" title="Chaos theory">chaotic</a> recurrence relation, the variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> stays in a bounded region but never converges to a fixed point or an attracting cycle; any fixed points or cycles of the equation are unstable. See also <a href="Logistic_map" title="Logistic map">logistic map</a>, <a href="Dyadic_transformation" title="Dyadic transformation">dyadic transformation</a>, and <a href="Tent_map" title="Tent map">tent map</a>.

<div class="mw-heading mw-heading2"><h2 id="Relationship_to_differential_equations">Relationship to differential equations</h2></div>

When solving an <a href="Ordinary_differential_equation" title="Ordinary differential equation">ordinary differential equation</a> <a href="Numerical_ordinary_differential_equations" class="mw-redirect" title="Numerical ordinary differential equations">numerically</a>, one typically encounters a recurrence relation. For example, when solving the <a href="Initial_value_problem" title="Initial value problem">initial value problem</a>

<msup>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y'(t)=f(t,y(t)),\ \ y(t_{0})=y_{0},}</annotation>

</semantics>

</math><img src="./ab41347356191c89811652feb00a7b30399a1c8d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.351ex; height:3.009ex;" alt="{\displaystyle y'(t)=f(t,y(t)),\ \ y(t_{0})=y_{0},}" loading="lazy"></dd></dl>

with <a href="Euler's_method" class="mw-redirect" title="Euler's method">Euler's method</a> and a step size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy">, one calculates the values

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{0}=y(t_{0}),\ \ y_{1}=y(t_{0}+h),\ \ y_{2}=y(t_{0}+2h),\ \dots }</annotation>

</semantics>

</math><img src="./b6822e45d3cfebdf42123473712dcb91147321de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:49.088ex; height:2.843ex;" alt="{\displaystyle y_{0}=y(t_{0}),\ \ y_{1}=y(t_{0}+h),\ \ y_{2}=y(t_{0}+2h),\ \dots }" loading="lazy"></dd></dl>

by the recurrence

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \,y_{n+1}=y_{n}+hf(t_{n},y_{n}),t_{n}=t_{0}+nh}</annotation>

</semantics>

</math><img src="./4c12211aaf18a0c27a393a2c241676fa641f987e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:36.677ex; height:2.843ex;" alt="{\displaystyle \,y_{n+1}=y_{n}+hf(t_{n},y_{n}),t_{n}=t_{0}+nh}" loading="lazy"></dd></dl>

Systems of linear first order differential equations can be discretized exactly analytically using the methods shown in the <a href="Discretization" title="Discretization">discretization</a> article.

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Mathematical_biology">Mathematical biology</h3></div>

Some of the best-known difference equations have their origins in the attempt to model <a href="Population_dynamics" title="Population dynamics">population dynamics</a>. For example, the <a href="Fibonacci_number" class="mw-redirect" title="Fibonacci number">Fibonacci numbers</a> were once used as a model for the growth of a rabbit population.

The <a href="Logistic_map" title="Logistic map">logistic map</a> is used either directly to model population growth, or as a starting point for more detailed models of population dynamics. In this context, coupled difference equations are often used to model the interaction of two or more <a href="Population" title="Population">populations</a>. For example, the <a href="Nicholson%E2%80%93Bailey_model" title="Nicholson–Bailey model">Nicholson–Bailey model</a> for a host-<a href="Parasite" class="mw-redirect" title="Parasite">parasite</a> interaction is given by

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{t+1}=\lambda N_{t}e^{-aP_{t}}}</annotation>

</semantics>

</math><img src="./540843982e53b1ab4eb3e311601155403eb1bc1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.104ex; height:3.009ex;" alt="{\displaystyle N_{t+1}=\lambda N_{t}e^{-aP_{t}}}" loading="lazy"></dd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{t+1}=N_{t}(1-e^{-aP_{t}}),}</annotation>

</semantics>

</math><img src="./ad7911b25ef84bb1a16decf4c2631381bf46d368.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.834ex; height:3.176ex;" alt="{\displaystyle P_{t+1}=N_{t}(1-e^{-aP_{t}}),}" loading="lazy"></dd></dl>

with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{t}}</annotation>

</semantics>

</math><img src="./b930a180af3138b8cf9c3e6674b5713bf81ef295.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.692ex; height:2.509ex;" alt="{\displaystyle N_{t}}" loading="lazy"> representing the hosts, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{t}}</annotation>

</semantics>

</math><img src="./7bdf246d27d8dd80dc45c1a1eaac69d42ce532d6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.318ex; height:2.509ex;" alt="{\displaystyle P_{t}}" loading="lazy"> the parasites, at time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">.

<a href="Integrodifference_equation" title="Integrodifference equation">Integrodifference equations</a> are a form of recurrence relation important to spatial <a href="Ecology" title="Ecology">ecology</a>. These and other difference equations are particularly suited to modeling <a href="Voltinism" title="Voltinism">univoltine</a> populations.

<div class="mw-heading mw-heading3"><h3 id="Computer_science">Computer science</h3></div>

Recurrence relations are also of fundamental importance in <a href="Analysis_of_algorithms" title="Analysis of algorithms">analysis of algorithms</a>.<a href="#cite_note-5">[5]</a><a href="#cite_note-6">[6]</a> If an <a href="Algorithm" title="Algorithm">algorithm</a> is designed so that it will break a problem into smaller subproblems (<a href="Divide_and_conquer_algorithm" class="mw-redirect" title="Divide and conquer algorithm">divide and conquer</a>), its running time is described by a recurrence relation.

A simple example is the time an algorithm takes to find an element in an ordered vector with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> elements, in the worst case.

A naive algorithm will search from left to right, one element at a time. The worst possible scenario is when the required element is the last, so the number of comparisons is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">.

A better algorithm is called <a href="Binary_search_algorithm" class="mw-redirect" title="Binary search algorithm">binary search</a>. However, it requires a sorted vector. It will first check if the element is at the middle of the vector. If not, then it will check if the middle element is greater or lesser than the sought element. At this point, half of the vector can be discarded, and the algorithm can be run again on the other half. The number of comparisons will be given by

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{1}=1}</annotation>

</semantics>

</math><img src="./11c8046c70c7e0e84425b052f781db3fc6dc4cb9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.322ex; height:2.509ex;" alt="{\displaystyle c_{1}=1}" loading="lazy"></dd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{n}=1+c_{n/2}}</annotation>

</semantics>

</math><img src="./699eabecf7168ae8722419e7f516d7734ec2f7b6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:13.196ex; height:3.009ex;" alt="{\displaystyle c_{n}=1+c_{n/2}}" loading="lazy"></dd></dl>

the <a href="Time_complexity" title="Time complexity">time complexity</a> of which will be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log _{2}(n))}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log _{2}(n))}</annotation>

</semantics>

</math><img src="./bca0626f9c0b4e0eef3953d0e11471c15c807079.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.813ex; height:2.843ex;" alt="{\displaystyle O(\log _{2}(n))}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Digital_signal_processing">Digital signal processing</h3></div>

In <a href="Digital_signal_processing" title="Digital signal processing">digital signal processing</a>, recurrence relations can model feedback in a system, where outputs at one time become inputs for future time. They thus arise in <a href="Infinite_impulse_response" title="Infinite impulse response">infinite impulse response</a> (IIR) <a href="Digital_filter" title="Digital filter">digital filters</a>.

For example, the equation for a "feedforward" IIR <a href="Comb_filter" title="Comb filter">comb filter</a> of delay <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"> is:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{t}=(1-\alpha )x_{t}+\alpha y_{t-T},}</annotation>

</semantics>

</math><img src="./d25f8bbe225fb489a978bbbec0a5129689ed7cdb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.895ex; height:2.843ex;" alt="{\displaystyle y_{t}=(1-\alpha )x_{t}+\alpha y_{t-T},}" loading="lazy"></dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{t}}</annotation>

</semantics>

</math><img src="./f279a30bc8eabc788f3fe81c9cfb674e72e858db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.156ex; height:2.009ex;" alt="{\displaystyle x_{t}}" loading="lazy"> is the input at time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{t}}</annotation>

</semantics>

</math><img src="./0fe9554452b93508c9d2479414a45981ecc75a2d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.965ex; height:2.009ex;" alt="{\displaystyle y_{t}}" loading="lazy"> is the output at time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math><img src="./b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy"> controls how much of the delayed signal is fed back into the output. From this we can see that

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{t}=(1-\alpha )x_{t}+\alpha ((1-\alpha )x_{t-T}+\alpha y_{t-2T})}</annotation>

</semantics>

</math><img src="./615c5aba81ebdafa05c7833956df7b620d228fef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:42.098ex; height:2.843ex;" alt="{\displaystyle y_{t}=(1-\alpha )x_{t}+\alpha ((1-\alpha )x_{t-T}+\alpha y_{t-2T})}" loading="lazy"></dd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{t}=(1-\alpha )x_{t}+(\alpha -\alpha ^{2})x_{t-T}+\alpha ^{2}y_{t-2T}}</annotation>

</semantics>

</math><img src="./bdb34e6f8e1030c7bd86deede456a46c9ece859d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:41.235ex; height:3.176ex;" alt="{\displaystyle y_{t}=(1-\alpha )x_{t}+(\alpha -\alpha ^{2})x_{t-T}+\alpha ^{2}y_{t-2T}}" loading="lazy"></dd></dl>

etc.

<div class="mw-heading mw-heading3"><h3 id="Economics">Economics</h3></div>

<div role="note" class="hatnote navigation-not-searchable">See also: <a href="Time_series_analysis" class="mw-redirect" title="Time series analysis">time series analysis</a> and <a href="Simultaneous_equations_model" title="Simultaneous equations model">simultaneous equations model</a></div>

Recurrence relations, especially linear recurrence relations, are used extensively in both theoretical and empirical economics.<a href="#cite_note-7">[7]</a><a href="#cite_note-8">[8]</a> In particular, in macroeconomics one might develop a model of various broad sectors of the economy (the financial sector, the goods sector, the labor market, etc.) in which some agents' actions depend on lagged variables. The model would then be solved for current values of key variables (<a href="Interest_rate" title="Interest rate">interest rate</a>, real <a href="GDP" class="mw-redirect" title="GDP">GDP</a>, etc.) in terms of past and current values of other variables.

/* start https://en.wikipedia.org/ */

.mw-parser-output .div-col{margin-top:0.3em;column-width:30em}.mw-parser-output .div-col-small{font-size:90%}.mw-parser-output .div-col-rules{column-rule:1px solid #aaa}.mw-parser-output .div-col dl,.mw-parser-output .div-col ol,.mw-parser-output .div-col ul{margin-top:0}.mw-parser-output .div-col li,.mw-parser-output .div-col dd{page-break-inside:avoid;break-inside:avoid-column}

/* end https://en.wikipedia.org/ */

</style><div class="div-col">

<ul><li><a href="Circle_points_segments_proof" class="mw-redirect" title="Circle points segments proof">Circle points segments proof</a></li>

<li><a href="Combinatorial_principles" title="Combinatorial principles">Combinatorial principles</a></li>

<li><a href="Continued_fraction" title="Continued fraction">Continued fraction</a></li>

<li><a href="Holonomic_function" title="Holonomic function">Holonomic sequences</a></li>

<li><a href="Infinite_impulse_response" title="Infinite impulse response">Infinite impulse response</a></li>

<li><a href="Integration_by_reduction_formulae" title="Integration by reduction formulae">Integration by reduction formulae</a></li>

<li><a href="Iterated_function" title="Iterated function">Iterated function</a></li>

<li><a href="Lagged_Fibonacci_generator" title="Lagged Fibonacci generator">Lagged Fibonacci generator</a></li>

<li><a href="Master_theorem_(analysis_of_algorithms)" title="Master theorem (analysis of algorithms)">Master theorem (analysis of algorithms)</a></li>

<li><a href="Mathematical_induction" title="Mathematical induction">Mathematical induction</a></li>

<li><a href="Orthogonal_polynomials" title="Orthogonal polynomials">Orthogonal polynomials</a></li>

<li><a href="Recursion" title="Recursion">Recursion</a></li>

<li><a href="Recursion_(computer_science)" title="Recursion (computer science)">Recursion (computer science)</a></li>

<li><a href="Time_scale_calculus" class="mw-redirect" title="Time scale calculus">Time scale calculus</a></li></ul>

</div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Footnotes">Footnotes</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><a href="#cite_ref-1">^</a> Jacobson, Nathan, Basic Algebra 2 (2nd ed.), § 0.4. pg 16.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <a rel="nofollow" class="external text" href="https://books.google.com/books?id=1klnDGelHGEC">Partial difference equations</a>, Sui Sun Cheng, CRC Press, 2003, <style data-mw-deduplicate="TemplateStyles:r1238218222">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-415-29884-1</bdi>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://faculty.pccu.edu.tw/%7Emeng/Math15.pdf">"Archived copy"</a> (PDF). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20100705023731/http://faculty.pccu.edu.tw/~meng/Math15.pdf">Archived</a> (PDF) from the original on 2010-07-05. Retrieved 2010-10-19.</cite><code class="cs1-code">{{cite web}}</code>: CS1 maint: archived copy as title (link)

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <a rel="nofollow" class="external text" href="https://www.techrxiv.org/doi/full/10.36227/techrxiv.174439127.75795694/v1">Solution of Nonhomogeneous Linear Recurrence Relations with Constant Coefficient based on Variation of Parameter</a>, Haoran Han, 2025

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> Cormen, T. et al, Introduction to Algorithms, MIT Press, 2009

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> R. Sedgewick, F. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, 2013

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFStokeyLucasPrescott1989" class="citation book cs1"><a href="Nancy_Stokey" title="Nancy Stokey">Stokey, Nancy L.</a>; <a href="Robert_Lucas%2C_Jr." class="mw-redirect" title="Robert Lucas, Jr.">Lucas, Robert E. Jr.</a>; <a href="Edward_C._Prescott" title="Edward C. Prescott">Prescott, Edward C.</a> (1989). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=BgQ3AwAAQBAJ">Recursive Methods in Economic Dynamics</a>. Cambridge: Harvard University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-674-75096-9</bdi>.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFLjungqvistSargent2004" class="citation book cs1"><a href="Lars_Ljungqvist" title="Lars Ljungqvist">Ljungqvist, Lars</a>; <a href="Thomas_J._Sargent" title="Thomas J. Sargent">Sargent, Thomas J.</a> (2004). <a rel="nofollow" class="external text" href="https://archive.org/details/recursivemacroec02edljun">Recursive Macroeconomic Theory</a> (Second ed.). Cambridge: MIT Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-262-12274-X</bdi>.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading3"><h3 id="Bibliography">Bibliography</h3></div>

<ul><li><cite id="CITEREFBatchelder1967" class="citation book cs1">Batchelder, Paul M. (1967). An introduction to linear difference equations. Dover Publications.</cite></li>

<li><cite id="CITEREFMiller1968" class="citation book cs1">Miller, Kenneth S. (1968). Linear difference equations. W. A. Benjamin.</cite></li>

<li><cite id="CITEREFFillmoreMarx1968" class="citation news cs1">Fillmore, Jay P.; Marx, Morris L. (1968). "Linear recursive sequences". SIAM Rev. Vol. 10, no. 3. pp. 324–353. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2027658">2027658</a>.</cite></li>

<li><cite id="CITEREFBrousseau1971" class="citation book cs1">Brousseau, Alfred (1971). <a rel="nofollow" class="external text" href="http://www.fq.math.ca/linear.html">Linear Recursion and Fibonacci Sequences</a>. Fibonacci Association.</cite></li>

<li><a href="Thomas_H._Cormen" title="Thomas H. Cormen">Thomas H. Cormen</a>, <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Charles E. Leiserson</a>, <a href="Ronald_L._Rivest" class="mw-redirect" title="Ronald L. Rivest">Ronald L. Rivest</a>, and <a href="Clifford_Stein" title="Clifford Stein">Clifford Stein</a>. <a href="Introduction_to_Algorithms" title="Introduction to Algorithms">Introduction to Algorithms</a>, Second Edition. MIT Press and McGraw-Hill, 1990. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-262-03293-7</bdi>. Chapter 4: Recurrences, pp. 62–90.</li>

<li><cite id="CITEREFGrahamKnuthPatashnik1994" class="citation book cs1">Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). Concrete Mathematics: A Foundation for Computer Science (2 ed.). Addison-Wesley. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-55802-5</bdi>.</cite></li>

<li><cite id="CITEREFEnders2010" class="citation book cs1">Enders, Walter (2010). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20141110221941/http://eu.wiley.com/WileyCDA/WileyTitle/productCd-EHEP000338.html">Applied Econometric Times Series</a> (3 ed.). Archived from <a rel="nofollow" class="external text" href="http://eu.wiley.com/WileyCDA/WileyTitle/productCd-EHEP000338.html">the original</a> on 2014-11-10.</cite></li>

<li><cite id="CITEREFCullFlahiveRobson2005" class="citation book cs1">Cull, Paul; <a href="Mary_Flahive" title="Mary Flahive">Flahive, Mary</a>; Robson, Robbie (2005). <a href="Difference_Equations%3A_From_Rabbits_to_Chaos" title="Difference Equations: From Rabbits to Chaos">Difference Equations: From Rabbits to Chaos</a>. Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-23234-6</bdi>.</cite> chapter 7.</li>

<li><cite id="CITEREFJacques2006" class="citation book cs1">Jacques, Ian (2006). <a rel="nofollow" class="external text" href="https://archive.org/details/mathematicsforec00jacq">Mathematics for Economics and Business</a> (Fifth ed.). Prentice Hall. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/mathematicsforec00jacq/page/n561">551</a>–568. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-273-70195-9</bdi>.</cite> Chapter 9.1: Difference Equations.</li>

<li><cite id="CITEREFMinhVan_To2006" class="citation web cs1">Minh, Tang; Van To, Tan (2006). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20160304035925/http://www.wseas.us/e-library/conferences/2006lisbon/papers/517-481.pdf">"Using generating functions to solve linear inhomogeneous recurrence equations"</a> (PDF). Proc. Int. Conf. Simulation, Modelling and Optimization, SMO'06. pp. 399–404. Archived from <a rel="nofollow" class="external text" href="http://www.wseas.us/e-library/conferences/2006lisbon/papers/517-481.pdf">the original</a> (PDF) on 2016-03-04. Retrieved 2014-08-07.</cite></li>

<li><cite id="CITEREFPolyanin" class="citation web cs1">Polyanin, Andrei D. <a rel="nofollow" class="external text" href="http://eqworld.ipmnet.ru/en/solutions/fe.htm">"Difference and Functional Equations: Exact Solutions"</a>.</cite> at EqWorld - The World of Mathematical Equations.</li>

<li><cite id="CITEREFPolyanin" class="citation web cs1">Polyanin, Andrei D. <a rel="nofollow" class="external text" href="http://eqworld.ipmnet.ru/en/education/edu-fe.htm">"Difference and Functional Equations: Methods"</a>.</cite> at EqWorld - The World of Mathematical Equations.</li>

<li><cite id="CITEREFWangWong2012" class="citation journal cs1">Wang, Xiang-Sheng; Wong, Roderick (2012). "Asymptotics of orthogonal polynomials via recurrence relations". Anal. Appl. 10 (2): 215–235. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1101.4371">1101.4371</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1142%2FS0219530512500108">10.1142/S0219530512500108</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:28828175">28828175</a>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><cite class="citation cs2"><a rel="nofollow" class="external text" href="https://www.encyclopediaofmath.org/index.php?title=Recurrence_relation">"Recurrence relation"</a>, <a href="Encyclopedia_of_Mathematics" title="Encyclopedia of Mathematics">Encyclopedia of Mathematics</a>, <a href="European_Mathematical_Society" title="European Mathematical Society">EMS Press</a>, 2001 [1994]</cite></li>

<li><cite id="CITEREFWeisstein" class="citation web cs1"><a href="Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a> <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/RecurrenceEquation.html">"Recurrence Equation"</a>. <a href="MathWorld" title="MathWorld">MathWorld</a>.</cite></li>

<li><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://oeis.org/wiki/Index_to_OEIS:_Section_Rec">"OEIS Index Rec"</a>.</cite> <a href="OEIS" class="mw-redirect" title="OEIS">OEIS</a> index to a few thousand examples of linear recurrences, sorted by order (number of terms) and signature (vector of values of the constant coefficients)</li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1038841319">

/* start https://en.wikipedia.org/ */

.mw-parser-output .tooltip-dotted{border-bottom:1px dotted;cursor:help}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox authority-control" aria-labelledby="Authority_control_databases_frameless&#124;text-top&#124;10px&#124;alt=Edit_this_at_Wikidata&#124;link=https&#58;//www.wikidata.org/wiki/Q740970#identifiers&#124;class=noprint&#124;Edit_this_at_Wikidata1152" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Authority_control_databases_frameless&#124;text-top&#124;10px&#124;alt=Edit_this_at_Wikidata&#124;link=https&#58;//www.wikidata.org/wiki/Q740970#identifiers&#124;class=noprint&#124;Edit_this_at_Wikidata1152" style="font-size:114%;margin:0 4em">Authority control databases </div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">National</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4012264-5">Germany</a></li><li><a rel="nofollow" class="external text" href="https://id.loc.gov/authorities/sh85037879">United States</a></li><li><a rel="nofollow" class="external text" href="https://aleph.nkp.cz/F/?func=find-c&local_base=aut&ccl_term=ica=ph119449&CON_LNG=ENG">Czech Republic</a></li><li><a rel="nofollow" class="external text" href="https://www.nli.org.il/en/authorities/987007553021405171">Israel</a></li></ul></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><a rel="nofollow" class="external text" href="https://lux.collections.yale.edu/view/concept/9d8469dc-195a-4e15-9480-eb6f494c8601">Yale LUX</a></li></ul></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-08-02" href="https://en.wikipedia.org/wiki/?title=Recurrence_relation&oldid=1303878140">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>